package lsl.leetCode.year2023.test0203;

import java.util.HashMap;

/**
 * description:
 *
 * @author: liushengli
 * data: 2023/2/3
 */
//409. 最长回文串
public class test409 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("abccccdd"));
    }

    public static int longestPalindrome(String s) {
        int[] countArr = new int[128];
        for (int i = 0; i < s.length(); i++) {
            //记录每个字符出现的次数
            countArr[s.charAt(i)]++;
        }
        int count = 0;
        for (int num : countArr) {
            //获取出现奇数次的字符
            count += num % 2;
        }
        return count == 0 ? s.length() : s.length() - count + 1;
    }

    //贪心算法
    public static int longestPalindrome1(String s) {
        //对于每个字符 ch，假设它出现了 v 次，
        //我们可以使用该字符 v / 2 * 2 次，在回文串的左侧和右侧分别放置 v / 2 个字符 ch，其中 / 为整数除法。
        //例如若 "a" 出现了 5 次，那么我们可以使用 "a" 的次数为 4，回文串的左右两侧分别放置 2 个 "a"。
        //如果有任何一个字符 ch 的出现次数 v 为奇数（即 v % 2 == 1），那么可以将这个字符作为回文中心，注意只能最多有一个字符作为回文中心。
        //在代码中，我们用 ans 存储回文串的长度，由于在遍历字符时，ans 每次会增加 v / 2 * 2，因此 ans 一直为偶数。
        //但在发现了第一个出现次数为奇数的字符后，我们将 ans 增加 1，这样 ans 变为奇数，在后面发现其它出现奇数次的字符时，我们就不改变 ans 的值了。
        int[] count = new int[128];
        int length = s.length();
        for (int i = 0; i < length; ++i) {
            char c = s.charAt(i);
            count[c]++;
        }

        int ans = 0;
        for (int v : count) {
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }
}
